
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

using namespace std;
//时间复杂度：O(NlogN)；空间复杂度：O(logN)；

class Solution {
  public:
    void quickSort(vector<int>& numbers) {
        srand((unsigned)time(NULL));
        if (numbers.empty()) return;
        //快速排序
        quickSort(numbers, 0, numbers.size() - 1);
    }

    void quickSort(vector<int>& numbers, int l, int r) {
        //if (l >= r) return;
        if (l < r) {
            int rand_num = (rand()%(r-l+1) + l);
            std::swap(numbers[rand_num],numbers[r]);
            std::vector<int> p = partition(numbers, l, r);
            quickSort(numbers, l, p[0] - 1);
            quickSort(numbers, p[1] + 1, r);
        }
    }
    
    std::vector<int> partition(vector<int>& numbers, int l, int r) {

        int less = l - 1;
        int more = r;
        while (l < more) {
            if (numbers[l] < numbers[r]) {
                std::swap(numbers[++less], numbers[l++]);
            } else if (numbers[l] > numbers[r]) {
                std::swap(numbers[l], numbers[--more]);
            } else {
                ++l;
            }
        }
        std::swap(numbers[more], numbers[r]);
        return std::vector<int> {++less, more};
    };
};
